1. Field of the Invention
The present invention relates to a routing technique for use in a router with a cache, and more particularly to a router with a cache which is capable of raising a cache hit probability and reducing the capacity of the cache.
2. Description of the Related Art
A router for connecting plural terminals to plural networks needs to perform transfer or forwarding of a block (packet) of communication information in order to achieve communications over different networks. In each router, a packet inputted from a connected network is received by an interface and a forwarding table possessed by the router is searched according to a final destination address contained in the received packet to determine a number of a transmission interface from which the packet should be sent to a next-hop router or the destination. In such a way, the packet forwarding is performed.
A conventional routing method for rapidly determining a transmission interface by using a cache table provided in the router (hereinafter referred to as xe2x80x9crouter with a cachexe2x80x9d) will be described.
A router having a conventional cache, as disclosed in Japanese Patent Application Laid-Open No. 6-261078, has a forwarding table, a forwarding table retrieval system for retrieving the forwarding table, and a cache table for exact matching retrieval. First, a structure and a retrieval method of each table will be described.
As shown in FIG. 1, the forwarding table has a pair of a destination field and a transmission interface number field. The destination field specifies a string of consecutive bits in the direction from the uppermost bit thereof toward a lower-order bit, which indicates a network address. The length of the bit string in called a prefix length and the bit string is called a prefix. To represent such a prefix, the destination field consists of two pieces of information: Prefix bit string and Prefix length.
The prefix bit string is a bit string having the same bit length as address and stores a bit string which is required to be specified continuously from the uppermost bit. Although bits not specified may store any bit, it is assumed hereinafter that bit xe2x80x9c0xe2x80x9d is stored.
The prefix length is the number of bits required to be specified as the prefix from the uppermost bit of the prefix bit string.
For example, in the case where the network address is 32-bit address, when a prefix of 10000000 01000000 (separated every 8 bits by a space) is required to be specified from the uppermost bit, the prefix bit string is 10000000 01000000 00000000 00000000 (separated every 8 bits by a space) and the prefix length is 16. In a following description, a 32-bit string is frequently separated every 8 bits into four blocks such that each block is expressed by a decimal number and the four blocks are indicated by separating with dots (dotted decimal notation). Further, in the cage of 32-bit network address, sometimes the destination field (prefix) is expressed by decimal notation with dots indicating a prefix bit string followed by the prefix length separated with xe2x80x9c/xe2x80x9d. For example, the prefix of the above 32 bits is expressed as 129.64.0.0/16.
Further, the prefix length may be expressed in mask bit string. According to this method, the mask bit string is a bit string consisting of consecutive bits of 1 for the prefix length in the direction from the uppermost bit toward a lower-order bit of the network address and the remaining part consisting of consecutive bits of 0. In the above example, the mask bit string is 11111111 11111111 00000000 00000000 (separated every 8 bits by a space). A transmission interface number to which a packet should be transferred is written in the transmission interface number field of the forwarding table. As to a retrieval method of the forwarding table, a method called longest prefix match retrieval (hereinafter referred to as LPM) is employed. In this retrieval, for all entries, the destination address of a packet is compared with a prefix registered in the destination field of the forwarding table. In this comparison, it is determined whether the following bit strings (1) and (2) match with each other.
The bit string (1) is a bit string of consecutive bits corresponding to the prefix length of an entry, extracted from the destination address of a pocket in the direction from the uppermost bit toward a lower-order bit.
The bit string (2) is a bit string of consecutive bits corresponding to the prefix length of an entry, extracted from the prefix bit length of the entry in the direction from the uppermost bit toward a lower-order bit.
Although there is a possibility that plural entries in which the bit strings (1) and (2) match with each other may exist in the forwarding table, an entry having the longest prefix length of them is an entry which is a result of the LPM retrieval.
The cache table has a destination address field and a transmission interface number field. Network addresses are written in the destination address field. In the transmission interface number field, transmission interface numbers are written and a packet whose destination address is the network address written in a corresponding destination address field is forwarded to that interface number. Upon retrieval, a destination address is given as a retrieval key and the cache is searched for an entry whose destination address field completely matches with the retrieval key.
In a router having a conventional cache, a process for determining a transmission interface number is carried out in the following manner. When a packet arrives at the router, the destination address of the packet is picked out. Then, with the destination address as a retrieval key, exact matching retrieval is carried out about the cache table. When a match is found, the interface number to which that packet should be transferred is obtained from the transmission interface number field of that entry. When no match is found, the forwarding table retrieval system carries out the LPM retrieval described above based on the destination field of the packet so as to obtain the transmission interface number.
When the forwarding table is retrieved, the destination address of the packet and the transmission interface number obtained from the table retrieval are stored in the cache in pair. In the aforementioned router having the conventional cache, a previously retrieved destination address of a packet and a result of the LPM retrieval are stored in a cache which can provide retrieval at higher speeds than the forwarding table retrieval. In the case where a packet having the same destination address arrives, a transmission interface number can be obtained by only cache retrieval. As a result, by omitting the forwarding table retrieval which takes longer than the cache retrieval, the interface-number determining processing, that is, path determining processing, is accelerated.
In the conventional cache as described above, however, the destination address of a packet is stored in the cache and the exact matching retrieval is carried out. Thus, the destination address which matches with the cache entry is only one. Therefore, the cache hit probability is low. When no hit is found in the cache, the forwarding table needs to be retrieved. Thus, it takes long until the transmission interface is determined and there is a problem that the packet transmission performance of the router is reduced. Further, when transmission is carried out to N destination addresses through a router, N cache entries are needed in order that a hit for each of these packets can be found in the cache. In other words, the number of cache entries must be identical to that of destination addresses. Thus, when the number of transmission terminals is large, it is necessary to mount a large capacity cache proportional thereto, and consequently, a circuit area of the router increases, thereby leading to an increase of production cost.
Accordingly, an object of the present invention is to provide a router having a cache therein, in which the entry hit probability of the cache is increased and a probability of carrying out forwarding table retrieval, which takes longer than the cache retrieval, is lowered, thereby decreasing packet processing time of the router to improve the packet processing performance of the router.
Another object of the present invention is to provide a router with a cache which allows a circuit area of the router to be reduced by decreasing the capacity of the cache without decreasing the entry hit probability of the cache.
According to an aspect of the present invention, a router for determining a forwarding direction of a received packet by referring to a cache table and a forwarding table depending on a destination address of the received packet, comprises:
a forwarding table retriever for retrievably storing a plurality of entries;
a cache table retriever for retrievably storing a plurality of cache entries, the cache table retriever capable of retrieval using a different mask for each cache entry;
a cache address determiner for determining a cache address at which a cache entry is registered; and
a cache prefix length determiner for determining a cache prefix length as a length of upper bits of the destination address of the received packet which are not masked by a corresponding mask.
The cache prefix length determiner determines a maximum cache prefix length based on cache entries. Alternatively, the cache prefix length determiner determines an optimum cache prefix length based on cache entries.
According to another aspect of the present invention, a router for determining a forwarding direction of a received packet by referring to a cache table and a forwarding table depending on a destination address of the received packet, comprises:
a forwarding table retriever for retrievably storing a plurality of entries;
a cache table retriever for retrievably storing a plurality of cache entries, the cache table retriever capable of longest prefix match (LPM) retrieval;
a cache address determiner for determining a cache address at which a cache entry is registered; and
a table manager for managing the forwarding table in form of tree topology to determine which entry is to be registered into the cache table and to be deleted from the cache table based on a result of retrieval on the forwarding table.
According to still another aspect of the present invention, a router for determining a forwarding direction of a received packet by referring to a cache table and a forwarding table depending on a destination address of the received packet, comprises:
a forwarding table retriever for retrievably storing a plurality of entries;
a cache table retriever for retrievably storing a plurality of cache entries, the cache table retriever capable of longest prefix match (LPM) retrieval;
a cache address determiner for determining a cache address at which a cache entry is registered; and
a cache prefix length determiner for determining a cache prefix length used when registering the destination address of the received packet into the cache table.
As described above, according to the present invention, (1) a cache capable of carrying out matching retrieval with a different mask for each entry or (2) a cache capable of carrying out longest prefix match (LPM) is used as a cache table capable of retrieving more rapidly than the forwarding table in a router. Therefore, a cache entry which hits plural destination addresses with only a single cache entry can be registered in the cache.
The forwarding table is searched using the destination address of a received packet as a key and a result of the retrieval is registered in the cache. To obtain a proper forwarding direction when the cache is searched, in the case of (1), a cache entry with a mask in registered using a means for obtaining the longest cache prefix length as a length of a not-masked portion of the cache entry or a means for obtaining an optimum cache prefix length. In the case of (2), the cache entry is registered using a means for determining an entry of the forwarding table to be registered into the cache table based on an entry hit by the retrieval on the forwarding table.
Upon registration, at which address of the cache table an entry should be registered is determined using a means for determining the cache address for registering a cache entry into the cache. Since a cache entry which hits plural destination addresses with a single cache entry can be registered as described above, according to the present invention, the cache hit probability can be raised.
In the case where transmission is carried out to plural different destination addresses through a router, in the conventional router, the same number of the cache entries as that of the different destination addresses is needed to make these destination addresses found in the cache. However, according to the present invention, the cache entry capable of hitting plural destination addresses can be registered with a single cache entry. Therefore, the cache can be hit by these destination packets with a smaller entry number than conventionally. Thus, the cache capacity can be reduced without lowering the cache hit probability, so that the circuit area of the router can be reduced.
As a means for determining a cache address for registering a cache entry in the cache, the entire address region is divided into a resident region and an updating region. When a means for determining the cache address from the updating region is used, the router manager can store an entry often used in the forwarding table onto the resident region. Further, those entries are never deleted when the other cache entry is registered. Therefore, the cache hit probability can be further raised.